package dp.base;

import java.util.Arrays;

public class Solution_198 {

    int[] memo;
    public int rob(int[] nums) {
        memo=new int[nums.length+1];
        Arrays.fill(memo,-1);
        return dfs(nums.length-1,nums);
    }

    private int dfs(int i,int[] nums) {
        if(i<0)
            return 0;
        if(memo[i]!=-1)
            return memo[i];
        return memo[i]=Math.max(dfs(i-1,nums),dfs(i-2,nums)+nums[i]);
    }


    public static void main(String[] args) {
        Solution_198 solution198 = new Solution_198();
        System.out.println(solution198.rob(new int[]{1, 2, 3, 1}));
    }
}
